
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1590. -- [Usaco2008 Dec]Secret Message -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1590: [Usaco2008 Dec]Secret Message</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>32 MB<br><span class=green>Submit: </span>60&nbsp;&nbsp;<span class=green>Solved: </span>44<br>[<a href='submitpage.php?id=1590'>Submit</a>][<a href='problemstatus.php?id=1590'>Status</a>][<a href='bbs.php?id=1590'>Discuss</a>]</center><h2>Description</h2><div class=content>Bessie is leading the cows in an attempt to escape! To do this, the
cows are sending secret binary messages to each other.

Ever the clever counterspy, Farmer John has intercepted the first
b_i (1 <= b_i <= 10,000) bits of each of M (1 <= M <= 50,000) of
these secret binary messages.

He has compiled a list of N (1 <= N <= 50,000) partial codewords
that he thinks the cows are using. Sadly, he only knows the first
c_j (1 <= c_j <= 10,000) bits of codeword j.

For each codeword j, he wants to know how many of the intercepted
messages match that codeword (i.e., for codeword j, how many times
does a message and the codeword have the same initial bits).  Your
job is to compute this number.

The total number of bits in the input (i.e., the sum of the b_i and
the c_j) will not exceed 500,000.

给定了N个模板串和M个匹配串，定义一个匹配串和一个模板串相互匹配的条件是它们的
最长前缀的长度等于两者中较短者的长度。要求找出每一匹配串与多少个模板串相匹配。</div><h2>Input</h2><div class=content>* Line 1: Two integers: M and N

* Lines 2..M+1: Line i+1 describes intercepted code i with an integer
        b_i followed by b_i space-separated 0's and 1's

* Lines M+2..M+N+1: Line M+j+1 describes codeword j with an integer
        c_j followed by c_j space-separated 0's and 1's

</div><h2>Output</h2><div class=content>* Lines 1..N: Line j: The number of messages that the jth codeword
        could match.
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>4 5<br />
3 0 1 0<br />
1 1<br />
3 1 0 0<br />
3 1 1 0<br />
1 0<br />
1 1<br />
2 0 1<br />
5 0 1 0 0 1<br />
2 1 1<br />
<br />
INPUT DETAILS:<br />
<br />
Four messages; five codewords.<br />
The intercepted messages start with 010, 1, 100, and 110.<br />
The possible codewords start with 0, 1, 01, 01001, and 11.<br />
<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>1<br />
3<br />
1<br />
1<br />
2<br />
<br />
</span></div><h2>HINT</h2>
			<div class=content><p>0 matches only 010: 1 match<br />
1 matches 1, 100, and 110: 3 matches<br />
01 matches only 010: 1 match<br />
01001 matches 010: 1 match<br />
11 matches 1 and 110: 2 matches<br />
</p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Gold'>Gold</a></p></div><center>[<a href='submitpage.php?id=1590'>Submit</a>][<a href='problemstatus.php?id=1590'>Status</a>][<a href='bbs.php?id=1590'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
